Huffman encoding algorithm is widely used in compression of video and image data, for example in JPEG and MPEG compression. As known, identical symbols (e.g. A, B, C, etc.) included in a file to be compressed may be repeatedly occurred. Based on the frequency of occurrence of the symbols in the file that is being compressed, Huffman encoding algorithm encodes symbols by assigning thereto respective codewords having lengths corresponding to probabilities of occurrence of the symbols. In a case that the occurrence of a symbol is more frequent, the length of the encoded symbol is shorter. Take a file having data ABCBCDCDDD for example. The frequency of occurrence for the symbol A is 1, for the symbol B is 2, for the symbol C is 3 and for the symbol D is 4. Since the symbol D has the most probable occurrence, the symbol D is assigned with a codeword having the shortest code length or bit-size. In contrast, since the symbol A has the least probable occurrence, the symbol A is assigned with a codeword having the longest code length or bit-size. For example, the symbol A is assigned with a codeword “11111111”, the symbol B is assigned with a codeword “00000”, the symbol C is assigned with a codeword “111” and the symbol D is assigned with a codeword “00”. By assigning smaller codes to more frequently used symbols and larger codes for less frequently used symbols, Huffman compression is a variable-length encoding system of reducing the size of files being compressed.
For reading the contents of the original file, the compressed file should be decompressed and then decoded by using a Huffman table as shown in FIG. 1. Referring to FIG. 1, the Huffman table includes several columns such as an address column, a symbol column, a size column and a codeword column. The address column denotes the address of the codeword stored in the memory. The size column denotes the bit-size of the codeword. The codeword column denotes the Huffman code of the encoded symbol. For example, the symbol J shown in FIG. 1 is assigned with a codeword “0110110” having a bit size of 7 (i.e. 7 bits). In other words, the input data “0110110” are encoded by the Huffman decoder into a corresponding symbol J and the bit-size is 7.
Nowadays, a nice way of visualizing the process of decoding a file compressed with Huffman encoding is to use a binary tree. A Huffman decoding method of using a binary tree-based search was disclosed in U.S. Pat. No. 6,621,429. According to the binary tree-based search, the Huffman table describes a binary tree corresponding to the Huffman code. Starting from the uppermost node, each node has two branches connected thereto so as to construct the binary tree.
Please refer to FIG. 2, which is a schematic view showing a binary tree created from the Huffman table of FIG. 1. Generally, if the Huffman table is changed, the configurations of the binary tree are varied. The binary tree of FIG. 2 stores each data (symbol) in a corresponding leaf node. By a Huffman decoder, a symbol search begins at the root of a binary tree and ends at any of the leaves. One bit for each node is extracted from bit-stream while traversing the binary tree. The code for a symbol is obtained by following the path from the root to the leaf node containing that symbol. The low-level bit 0 of the input data is assigned to a left branch, and the high-level bit 1 is assigned to a right branch. After a symbol corresponding to the bit is searched, a next bit of the input data is extracted and then decoded as described above.
For example, an input data stream “011101” to be decoded is illustrated with reference to FIG. 2. As to the node 11, the first bit data “0” is assigned to the left branch to the node 12. As to the node 12, the second bit data “1” is assigned to the right branch to the node 13. As to the node 13, the third bit data “1” is assigned to the right branch to the node 14. As to the node 14, the fourth bit data “1” is assigned to the right branch to the node 19. As to the node 19, the fifth bit data “0” is assigned to the left branch to the node 20. As to the node 20, the sixth bit data “1” is assigned to the right branch to the leaf node storing that symbol F. That is, the input data stream “011101” may be decoded into the symbol F. After the leaf node is searched, a new input data stream is continuously read and a symbol search begins at the root node 11 again. The binary tree search procedures are repeated until all input data streams are recoded.
Since the bits of the input data stream are decoded one by one, the processing speed of such binary tree search method is very slow and is not suitable to decode abundant compressed files. Therefore, there is a need to provide a Huffman decoding method for decoding Huffman codes at a high speed.